package com.lun.medium;

public class UniquePathsII {
	
	//方法一：动态规划（二维数组）
	public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		int m = obstacleGrid.length, n = obstacleGrid[0].length;
		int[][] dp = new int[m][n];
		
        for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
        	dp[i][0] = 1;
        }
        
        for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) { 
        	dp[0][j] = 1;
        }
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) 
                	continue;
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
		return dp[m - 1][n - 1];
	}
	
	//方法二：动态规划（一维数组）
    public int uniquePathsWithObstacles2(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        
        int[] dp = new int[n]; 
        int firstRowBlockIndex = n, firstColBlockIndex = m;
        for(int i = 0; i < m; i++) {
        	for(int j = 0; j < n; j++) {
        		if(obstacleGrid[i][j] == 1) {
        			if(i == 0 && firstRowBlockIndex == n) {        				
        				firstRowBlockIndex = j;
        			}
        			if(j == 0 && firstColBlockIndex == m) {
        				firstColBlockIndex = i;
        			}
        			dp[j] = 0;
        			continue;
        		} 
        		
        		if(i == 0 || j == 0) {
        			dp[j] = (i == 0 && j >= firstRowBlockIndex ||
        					j == 0 && i >= firstColBlockIndex) ? 0 : 1;
        		}else if(j > 0){
        			dp[j] += dp[j - 1];
        		}
        	}
        }
        
    	return dp[n - 1];
    }
}
